package org.example.game.history;

import java.util.Arrays;
import java.util.HashMap;

/**
 * @Description: TODO
 * @Author wyatt
 * @Data 2024/05/26 10:31
 */
public class Solution100323 {

    public static void main(String[] args) {

        Solution100323 solution100323 = new Solution100323();

//        int[] nums1 = new int[100000];
//        int[] nums2 = new int[100000];
//
//        for(int i=0;i<100000;i++){
//            if(i % 2 == 0){
//                nums1[i] = 4;
//                nums2[i] = 1;
//            }else {
//                nums1[i] = 8;
//                nums2[i] = 2;
//            }
//        }

        int[] nums1 = new int[]{1,5,18};
        int[] nums2 = new int[]{16,19,1};

        System.out.println(solution100323.numberOfPairs2(nums1, nums2, 2));
    }

    public int numberOfPairs(int[] nums1, int[] nums2, int k) {

        int n = nums1.length;
        int m = nums2.length;

        int sum = 0;

        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(nums1[i] % (nums2[j] * k) == 0 ){
                    sum++;
                }
            }
        }

        return sum;
    }

    public long numberOfPairs2(int[] nums1, int[] nums2, int k) {

        // 1. 过滤
        // nums2 排序
        int n = nums1.length;
        int m = nums2.length;

        long sum = 0;

        for(int i=0;i<n;i++){
            if(nums1[i] % k == 0){
                nums1[i] = nums1[i] / k;
            }else {
                nums1[i] = Integer.MAX_VALUE;
            }
        }

        Arrays.sort(nums1);
        Arrays.sort(nums2);

        HashMap<Integer, Integer> num1Map = new HashMap<>();
        HashMap<Integer, Integer> num2Map = new HashMap<>();

        for(int i=0;i<nums1.length;i++){
            if(num1Map.containsKey(nums1[i])){
                num1Map.put(nums1[i], num1Map.get(nums1[i]) + 1);
            }else {
                num1Map.put(nums1[i], 1);
            }
        }

        for(int i=0;i<nums2.length;i++){
            if(num2Map.containsKey(nums2[i])){
                num2Map.put(nums2[i], num2Map.get(nums2[i]) + 1);
            }else {
                num2Map.put(nums2[i], 1);
            }
        }

        for(int num1 : num1Map.keySet()){
            if(num1 == Integer.MAX_VALUE){
                continue;
            }


            long subCount = 0;
            for(int num2 : num2Map.keySet()){
                if(num2 > num1){
                    continue;
                }
                if(num1 % num2 == 0 ){
                    subCount += num2Map.get(num2);
                }
            }

            sum = sum + (subCount * num1Map.get(num1));
        }

        return sum;
    }

}
